package Exams.UCloud;

import java.util.Arrays;
import java.util.PriorityQueue;

public class q1 {

    /*
    主持人调度
     */
    public int minmumNumberOfHost_1 (int n, int[][] startEnd) {
        Arrays.sort(startEnd, (a, b) -> a[0] <= b[0] ? -1 : 1);
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        int ans = 0;
        for (int[] interval : startEnd) {
            while (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
                minHeap.poll();
            }
            minHeap.add(interval[1]);
            ans = Math.max(ans, minHeap.size());
        }
        return ans;
    }

    public int minmumNumberOfHost_2 (int n, int[][] startEnd) {
        // write code here
        int[] start = new int[startEnd.length];
        int[] end = new int[startEnd.length];

        for (int i = 0; i < startEnd.length; i ++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int res = 0;
        int index = 0;
        for (int i = 0; i < startEnd.length; i ++) {
            if (start[i] < end[index]) {
                res ++;
            } else {
                index++;
            }
        }

        return res;
    }
}
